/**
 * 岛屿数量
 * @param numCourses
 * @param prerequisites
 */
const canFinish = (numCourses: number, prerequisites: number[][]): boolean => {
  const visited: number[] = new Array(numCourses).fill(0);

  const edges: Record<number, number> = {};

  const len = prerequisites.length;
  for (let i = 0; i < len; i++) {
    edges[prerequisites[i][1]] = prerequisites[i][0];
  }

  let valid = true;

  const dfs = (u: number) => {
    visited[u] = 1;
    const v = edges[u];
    // 如果v还是0
    if (visited[v] === 0) {
      dfs(v);
      // 如果无效了, 直接返回
      if (!valid) return;
    } else if (visited[v] === 1) {
      // 这个已经访问过了, 直接返回
      valid = false;
      return;
    }
    // 标记为2
    visited[u] = 2;
  };

  for (let i = 0; i < numCourses && valid; i++) {
    if (visited[i] === 0) {
      dfs(i);
    }
  }

  return valid;
};

const canFinish2 = (numCourses: number, prerequisites: number[][]): boolean => {
  const visited: number[] = new Array(numCourses).fill(0);

  const edges: number[][] = [];
  // 初始化edges
  for (let i = 0; i < numCourses; i++) {
    edges.push(new Array(2));
  }

  const len = prerequisites.length;
  for (let i = 0; i < len; i++) {
    edges[prerequisites[i][1]].push(prerequisites[i][0]);
  }

  let valid = true;

  const dfs = (u: number) => {
    visited[u] = 1;
    const vals = edges[u];
    for (let v of vals) {
      // 如果v还是0
      if (visited[v] === 0) {
        dfs(v);
        // 如果无效了, 直接返回
        if (!valid) return;
      } else if (visited[v] === 1) {
        // 这个已经访问过了, 直接返回
        valid = false;
        return;
      }
    }
    // 标记为2
    visited[u] = 2;
  };

  for (let i = 0; i < numCourses && valid; i++) {
    if (visited[i] === 0) {
      dfs(i);
    }
  }

  return valid;
};
